Bringer et al. proposed two cryptographic protocols for the computation of Hamming distance. Their first scheme usesOblivious Transfer and provides security in the semi-honest model. The other scheme uses Committed Oblivious Transferand is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometricauthentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form.In this paper, we show that their protocol is not actually fully secure against malicious adversaries. More precisely, ourattack breaks the soundness property of their protocol where a malicious user can compute a Hamming distance which isdifferent from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass theauthentication without knowledge of the honest user’s input with at most O(n) complexity instead of O(2n), where n isthe input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of ourmodified protocol is proven using the simulation-based paradigm. Furthermore, as for efficiency concerns, the modifiedprotocol utilizes Verifiable Oblivious Transfer which does not require the commitments to outputs which improves itsefficiency significantly.
展开▼
